CS 235 Midterm topics


Chapter 5

Given a code fragment, determine the big-oh running time.

Given an algorithm that takes time t on size n, 
determine the time on size k.

Given an algorithm that takes time t on size n, 
determine the size in time r.

Given a table of empirical results with size and time,
determine the big-oh function that best describes the time.

Given a list of big-oh functions in an arbitrary order,
sort the functions in order of growth.

Estimate the logarithm of a number.
Use the halving/doubling principle to find logarithmic BigOhs.

Given an array of values and an item x to search for,
determine the part of the array in which x could still
be found after each major step of binary search.


Chapter 6

Know what an Iterator is and what its operations do.

Know the behavior of each standard operation for each data type.
list (get, set, add, remove, contains)
stack (push, pop, top)
queue (enqueue, dequeue, getFront)
set (add, remove, contains)
map (get, put, remove, containsKey)
priority queue (insert, findMin, deleteMin)

Given a brief description of an application, choose the data type that
is most effective when implementing the application.


Chapter 7  
Know the rules of recursion.
Examples of recursion:  Merge sort, quick sort, Fibonacci

Give a running time equation (T(n)) for recursive code.


Chapter 8

Determine the content of an array after each major step of insertion
sort.

Determine the content of an array after each major step of selection
sort.

Determine the content of an array in the middle of mergesort after the
two recursive calls to mergesort have completed but before the call to
merge.

Determine the content of an array in the middle of quicksort after the
array has been partitioned but before the two recursive calls to
quicksort.

Know the average case, worst case, and best case big-oh for the following 
algorithms:  selection sort, merge sort, insertion sort, quick sort, 
quick select, binary search